package com.es.www.structure.linkedList;

import java.util.List;
import java.util.Objects;

import org.assertj.core.util.Lists;

/**
 * @Created by michangtao
 * @Date 2022/10/18 13:58
 * @Description 链表
 */
public class LinkedList<E> {

    private Node<E> head;
    private Node<E> tail;
    private int size;

    public int getSize() {
        return size;
    }

    public static class Node<E> {
        private E e;
        private Node<E> next;
        private Node<E> prev;

        public Node(E e, Node<E> next, Node<E> prev) {
            this.e = e;
            this.next = next;
            this.prev = prev;
        }
    }

    /**
     * 尾插法
     * @param e
     */
    public void linkLast(E e) {
        //将原尾结点记录下来
        final Node<E> oriTail = tail;
        //创建一个新节点
        Node<E> newNode = new Node<>(e, null, oriTail);
        //指定新节点为尾结点
        tail = newNode;
        if (oriTail == null) {
            //如果没有尾结点，说明链表不存在(如果链表只有一个元素，则head、tail均为同一个节点)，直接将新节点置为头结点
            head = newNode;
        }
        else {
            //原尾结点指向新的节点
            oriTail.next = newNode;
        }
        size ++;

    }

    /**
     * 头插法
     * @param e
     */
    public void linkFirst(E e) {
        final Node<E> oriHead = head;
        Node<E> newNode = new Node<>(e, oriHead, null);
        head = newNode;
        if(oriHead == null){
            tail = newNode;
        }else {
            oriHead.prev = newNode;
        }
        size ++;
    }

    /**
     * 拆链
     * @param x
     * @return
     */
    private E unLink(Node<E> x){
        //记录删除节点信息
        final E element = x.e;
        final Node<E> oldPrev = x.prev;
        final Node<E> oldNext = x.next;

        //如果要删除的节点是头结点
        if(oldPrev == null){
            //设置新的头结点
            head = oldNext;
        }else {
            oldPrev.next = oldNext;
            x.prev = null;
        }

        //如果要删除的节点是尾结点
        if(oldNext == null){
            tail = oldPrev;
        }else {
            oldNext.prev = oldPrev;
            x.next = null;
        }
        x.e = null;
        size--;
        return element;
    }

    public Boolean remove(E item){
        for (Node<E> x=head; x!=null; x=x.next){
            if(item == null && x.e == null){
                unLink(x);
                return true;
            }else if(item !=null && item.equals(x.e)){
                unLink(x);
                return true;
            }
        }
        return false;
    }

    /**
     * 打印链表
     * @return
     */
    public List<E> printList(){
        List<E> list = Lists.newArrayList();
        list.add(head.e);
        Node<E> forNode = head;
        while(forNode.next !=null){
            list.add(forNode.next.e);
            forNode = forNode.next;
        }
        return list;
    }
}
